// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-19 12:48
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSumByTwoPointer {
    /**
     * 使用双指针解法解决两数之和
     * 使用四指针解决四数之和
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
            return res;
        }
        Arrays.sort(nums);
        int cur = 0, n = nums.length;
        for (int p = 0; p < n - 3; p++) {
            /*
                判断当前组合的最小值和最大值与target的关系，如果最小值大于target或最大值小于target说明p不适合
                最小值:break  最大值:continue
             */
            if (p > 0 && nums[p] == nums[p - 1]) {
                // [2,2,2,2] -> 因为i 的取值范围限定了
                continue;
            }
            cur = nums[p] + nums[n - 3];
            if (cur < (target - nums[n - 2] - nums[n - 1])) {
                /*
                    最大值小于目标值，当前组合不存在解
                 */
                continue;
            }
            cur = nums[p] + nums[p + 1];
            if (cur > (target - nums[p + 2] - nums[p + 3])) {
                /*
                    最小值大于目标值，当前组合不存在解
                 */
                break;
            }
            // 当前组合可能存在解，开始第二层循环
            for (int q = p + 1; q < n - 2; q++) {
                /**
                 *  重复判断最小和最大值和目标值的关系
                 */
                if (q > (p + 1) && nums[q] == nums[q - 1]) {
                    // 算法是如何避免重复答案的？
                    continue;
                }
                cur = nums[p] + nums[q];
                int h = q + 1, t = n - 1;

                if (cur < (target - nums[t] - nums[t - 1])) {
                    continue;
                }
                if (cur > (target - (nums[h] + nums[h + 1]))) {
                    break;
                }
                // 当前组合可能存在解
                while (h < t) {
                    cur = nums[p] + nums[q] + nums[h] + nums[t];
                    if (cur == target) {
                        res.add(Arrays.asList(nums[p], nums[q], nums[h], nums[t]));
                        h++;
                        while (h < t && nums[h] == nums[h - 1]) {
                            // 如何避免数组越界
                            h++;
                        }
                        t--;
                        while (h < t && nums[t] == nums[t + 1]) {
                            t--;
                        }
                    } else if (cur > target) {
                        t--;
                    } else {
                        h++;
                    }
                }
            }
        }
        return res;
    }


    @Test
    public void shout() {
        int[] test = {0, 4, -5, 2, -2, 4, 2, -1, 4};
        int target = 12;
        System.out.println(fourSum(test, target));
    }
}
